如果現在有一個大小為 2N 的空陣列，然後連續進行加入 N 筆資料的操作。這些資料都有一個主要的鍵值可以拿來比較大小。但是插入資料的順序並不固定。在資料逐漸一筆一筆加入這個陣列的過程裡，可能隨時會有人來按照順序存取這些資料，所以我們會希望來存取時，這些資料在陣列裡面都按照順序排得好好的。

找出欲插入的資料要接在哪兩個資料中間，這件事情是容易的。於是我們可以假定，每一次操作都形如「緊接著在 x 後面插入 y」這樣的動作。此外，每一筆資料插入後，資料不一定要連續地擺在一起，但是從左到右必須要按照順序。我們可以在過程中移動資料。

在最壞情形下，最小的總搬移資料次數為何？

下面這篇文章告訴你說可以作到 的時間！大致的概念是，我們在陣列上面覆蓋一些區間，每一次插入以後，我們找出過度擁擠的區間，然後把他們重新等距離排好。這個概念其實跟另一種自毀型(?)二元搜尋樹：代罪羔羊樹(Scapegoat Tree) 概念相同，當一個子樹其數量與深度不成比例時，就把整棵子樹砍掉重練。這麼一來就可以作到 O(log N) 均攤複雜度了！

參考資料

https://courses.csail.mit.edu/6.851/spring07/scribe/lec20.pdf